#!/usr/bin/env python3
"""
@Project    ：learn-algorithm 
@File       ：queens_problem.py 
@Author     ：qqq
@Time       ：2024/4/17 8:49
@Annotation : “”
@ID: 20240417192021
"""

"""
四皇后问题解
共有 2 种解法
[1, 3, 0, 2]
[2, 0, 3, 1]

八皇后问题解
共有 92 种解法
略

Q:
八皇后是在 8×8 的国际棋盘上摆放 8 个皇后, 使其不能互相攻击
即任意两个皇后都不能处于同一行, 同一列或同一正反斜线上, 问有多少种摆法? 

四皇后问题是一张四乘四的棋盘, 在棋盘中放四颗棋子, 要求如下: 任意两个皇后都不能处在同一行, 同一列 任意两个皇后都不能处在同一斜线上(主斜线, 反斜线)

任意两个皇后都不能处在同一行, 同一列
任意两个皇后都不能处在同一斜线上(主斜线, 反斜线)
"""


def is_valid_queen(queens_positions, queen_idx):
    pos = queens_positions[queen_idx]

    for row in range(queen_idx - 1, -1, -1):
        if queens_positions[row] == pos:
            return False

    for row in range(queen_idx - 1, -1, -1):
        if queens_positions[row] == pos - (queen_idx - row):
            return False

    for row in range(queen_idx - 1, -1, -1):
        if queens_positions[row] == pos + (queen_idx - row):
            return False

    return True


def queens_position_put(queens_position, queen_idx, queen_num):
    if queen_idx >= queen_num:
        print(queens_position)
        return

    for col in range(queen_num):
        queens_position[queen_idx] = col

        if is_valid_queen(queens_position, queen_idx):
            queens_position_put(queens_position, queen_idx + 1, queen_num)
        else:
            queens_position[queen_idx] = -1

    return False


def main():
    queen_num = 4
    queens_positions = [-1] * queen_num
    queens_position_put(queens_positions, 0, queen_num)


if __name__ == '__main__':
    main()
